package 题目集.动态规划.状压dp;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 求把 N×M 的棋盘分割成若干个 1×2 的长方形，有多少种方案。 例如当 N=2，M=4 时，共有 5 种方案。当 N=2，M=3 时，共有 3
 * 种方案。 https://www.acwing.com/problem/content/293/ 这题的全枚举方式有点难想。 思路： 对于
 * 一个n*m的棋盘。枚举方式如下 我们只考虑当前列。 在当前列任意位置放1根横条，当前列的其他位置全放竖条。使得整个棋盘合法的方案有多少种。
 * 在当前列任意位置放2根横条，当前列的其他位置全放竖条。使得整个棋盘合法的方案有多少种。 .... 之后的列：
 * 也和之前的列一样枚举，但如果之前列有突出的位置，那么这个位置不能被枚举
 */
public class ch04_蒙德里安的梦想 {
	static int n, m;
	static int originState;
	static int maxN = 11;
	static long[][] dp = new long[maxN][1 << maxN];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (true) {
			n = sc.nextInt();
			m = sc.nextInt();
			if (n == 0)
				return;
			// 1表示空格，0表示不能放的位置
			originState = (1 << n) - 1;
			// m是列
			dp = new long[m][1 << n];
			for (long[] d : dp) {
				Arrays.fill(d, -1);
			}
			long res = dfs(0, originState);
			System.out.println(res);
		}
	}

	/**
	 * @param i：当前枚举的列
	 * @param state：前面突出的位置
	 * @return
	 */
	public static long dfs(int i, int state) {
		if (i == m) { // 已经枚举完所有列，是否还有突出
			return state == originState ? 1 : 0;
		}
		if (dp[i][state] != -1) {
			return dp[i][state];
		}
		// 当前行全放横条，下一行空格的位置
		int nextState = ~state & originState;
		//全部放横条的情况
		dp[i][state]= dfs(i + 1, nextState);	//相当于nextState | state的空集
		// 枚举state的所有非空子集，或者收枚举所有放竖条的情况
		for (int j = state; j > 0; j = (j - 1) & state) {
			if (check(j)) {
				int next = j | nextState;
				dp[i][state] += dfs(i + 1, next);
			}
		}
		return dp[i][state];
	}

	/**
	 * 当前列是否可以被竖条全部插满，即判断是否不存在奇数的空格
	 *
	 * @param state
	 * @return
	 */
	public static boolean check(int state) {
		int pre = 0;
		for (int i = 0; i < n; i++) {
			int tag = 1 << i;
			// 之前的连续的空格是否为偶数
			if ((tag & state) == 0) {
				if (pre % 2 != 0)
					return false;
			} else {
				pre++;
			}
		}
		return pre % 2 == 0;
	}
}
